package boggle;

import java.util.ArrayList;

/*
 * find all the words in this board
 * using algorithm from Stanford cs106B's boggle
 * great recursion algorithm!!!! 
 */

public class BoggleSolver {
	private static lexicon lex = new lexicon();
	public  static final int MINIMUM_WORD_LENGTH = 3;
	
	/**
	 * 
	 * @param board
	 * @return
	 */
	public static WordList solve(BoggleBoard board) {
		WordList wordsFound = new WordList();
		WordList res        = new WordList();
		for(int i = 0; i < board.size(); i++) {
			for(int j = 0; j < board.size(); j++) {
				String   location = i + ";" + j;
				ArrayList<String> pathTaken = new ArrayList<String>();
				pathTaken.add(location);
				findAllLeftWords(board, board.getCell(i, j), pathTaken, wordsFound, i , j);
			}
		}
		
		for (String word : wordsFound) {
			if (word.length() >= MINIMUM_WORD_LENGTH)
				res.add(word);
		}
		return  res;
	}
	
	/**
	 * Recursively found all the words in a BoggleBoard at (row, col)
	 * @param board : Boggle board
	 * @param prefix : String at the starting position 
	 * @param pathTaken : path of the word
	 * @param wordsFound : the result words list
	 * @param row : row index
	 * @param col : col index
	 */
	
	private static void findAllLeftWords(BoggleBoard board, String prefix,
			ArrayList<String> pathTaken, WordList wordsFound, int row, int col) {
		
		if (lex.containsWord(prefix) && !wordsFound.containsWord(prefix)) {
			wordsFound.add(prefix);
		}
		
		if (lex.containsPrefix(prefix)) {
			for(int r = row - 1; r <= row + 1; r++) {
				for(int c = col - 1; c <= col + 1; c++) {
					String loc = r + ";" + c;
					if (board.inBoardBound(r, c) && !listContains(pathTaken, loc)) {
						pathTaken.add(loc);
						String newPrefix = prefix + board.getCell(r, c);
						findAllLeftWords(board, newPrefix, pathTaken, wordsFound, r, c);
						pathTaken.remove(pathTaken.size() - 1);
					}
				}
			}
		}
					
	}

	/**
	 * Check whether an element  contains in ArrayList
	 * @param pathTaken, the ArrayList
	 * @param loc, the element
	 * @return : true if found
	 */

	private static boolean listContains(ArrayList<String> pathTaken, String loc) {
		return (pathTaken.indexOf(loc) != -1);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BoggleBoard bd = new BoggleBoard();
		System.out.println(bd);
		System.out.println("==============");
		WordList res = BoggleSolver.solve(bd);
		for (String word : res) 
			System.out.println(word);
	}

}
